Packet switching has been defined as the transmission of data between terminal equipments by means of addressed packets, whereby a transmission channel is occupied for the duration of transmission of the packet only. The channel is then available for use by packets being transferred between different terminal equipments.
A packet switch functions by accepting a message from an originating terminal or computer, inserting various kinds of network control information for error control, flow control, sequencing and the like; and then routing the packet through a path containing one or more packet switching nodes until it arrives at the destination node. The packets of the message are then checked for correctness and transmitted to the destination terminal or computer. Under certain protocols and at originating customer request, an end-to-end acknowledgment of packet transmissions is generated and transmitted back to the originating terminal or computer.
Packet switches and networks are currently available to offer a variety of interfaces to many different types of terminal equipments and computers. They provide a grade of service for customers by means of a set of communication protocols between adjacent switches and networks and from source to destination. The protocols insure that packets are delivered correctly or, in some cases when they cannot be delivered due to a failure, that the source is notified of that event. In addition, the protocols perform flow control so that the source is regulated to send no more traffic than the destination or packet switch can accept.
An international standard protocol for interfacing data terminals and computers to any packet switching network has been recommended by the Study Group VII of the CCITT (Consultative Committee of International Telegraph and Telephone). The protocol known as Recommendation X.25 provides rules on how to establish an access link to the packet switch network, set-up virtual circuits, and transfer data.
Recommendation X.25 entitled "Interface Between Data Terminal Equipment (DTE) and Data Circuit Terminating Equipment (DCE) For Terminals Operating In The Packet Mode On Public Networks" Yellow Book, Volume VIII--Fascicle VIII.2, page 100 et seq., dated 1981 for the VII Plenary Assembly Geneva, Nov. 10-21, 1980, has gained worldwide acceptance for use as a standard interface both to connect user data terminals and computers to domestic networks so that information communication may flow freely without any complications for the network customers.
In essence, X.25 provides precise procedures for a data terminal or computer first to obtain access to a packet switching network and then to establish one or more so-called virtual circuits and/or permanent virtual circuits each on a distinct logical channel through the network to a destination data terminal or computer. The protocol utilizes a D (Delivery Confirmation or Acknowledgment) bit in the packet information to indicate the type of acknowledgment desired for the data it is transmitting.
The D-bit in an X.25 data packet flags whether the acknowledgment (ACK) to the packet can be local or must be end-to-end. The ACK is given in one of three forms: in an RR (Receiver Ready) packet; in an RNR (Receiver Not Ready) packet, or piggybacked onto a data packet. If the value of the D-bit is 0 then the ACK may be local to the interface with the network. If the D-bit value is 1, then the ACK must be end-to-end. The latter ACK means that the packet's destination (the customer) must specifically send an ACK to the network before it can ACK back to the packet's source. This arrangement is complicated by the fact that, besides the D-bit option, the transport switching network implements its own congestion management. Resultingly, the network is required to track which packets may be acknowledged when permitted to do so by the congestion mechanism and the D-bit option.
The access protocol controls, on a per logical channel basis, "windows" to authorize data packets out to/from the customer, while the internal protocol on the same logical channel of the transport network controls "windows" of authorized data packets between switches of the transport network. There is one window for each direction of transmission for each protocol. The two protocols control their respective windows somewhat independent of each other. For example, suppose on one such logical channel the access window size is 2 and the internal window size is 4. Now suppose that the customer transmits a data packet: Data 0 with D-bit=0 (local ACK). The access window is dropped to 1, the internal window is dropped to 3, but because no end-to-end ACK is designated, the access protocol sends an ACK back immediately, and the window again becomes 2. However, the internal protocol window remains at 3.
Continuing, suppose the customer sends in two more data packets: Data 1 with D-bit=1 (end-to-end ACK) and Data 2 with D-bit=0 (local ACK). The access window is now closed (set to 0) as neither Data 1 nor Data 2 can be acknowledged before the ACK for Data 1 is received from the destination. In the meantime, the internal protocol of the transport network is transmitting all three packets to the destination and it has not received any ACKs at all so its window is 1. When the ACK comes in from the network for the Data 0 packet, the access protocol cannot ACK anything new as Data 1 packet has still not been ACKed. The internal window goes to 2. However, when the ACK for the Data 1 packet is received by the internal protocol, the access protocol is allowed to not only ACK the Data 1 packet to the originating customer, but also the Data 2 packet as its D-bit was zero. Thus, if both packets are now ACKed, the access window returns to 2, but the internal protocol window is at 3 (one Data packet (Data 2) outstanding).
A problem confronting the art has been the coordination of the D-bit activity and windows of the access protocol of the data terminal equipment and the internal protocol of the transport switching network.